{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Entropy maximization\n",
    "\n",
    "A derivative work by Judson Wilson, 6/2/2014.<br>\n",
    "Adapted from the CVX example of the same name, by Joëlle Skaf, 4/24/2008.\n",
    "\n",
    "## Introduction\n",
    "\n",
    "Consider the linear inequality constrained entropy maximization problem:\n",
    "    $$\\begin{array}{ll}\n",
    "    \\mbox{maximize}   & -\\sum_{i=1}^n x_i \\log(x_i) \\\\\n",
    "    \\mbox{subject to} & \\sum_{i=1}^n x_i = 1 \\\\\n",
    "                      & Fx \\succeq g,\n",
    "    \\end{array}$$\n",
    "where the variable is $x \\in \\mathbf{{\\mbox{R}}}^{n}$.   \n",
    "\n",
    "This problem can be formulated in CVXPY using the `entr` atom.\n",
    "\n",
    "## Generate problem data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cvxpy as cp\n",
    "import numpy as np\n",
    "\n",
    "# Make random input repeatable. \n",
    "np.random.seed(0) \n",
    "\n",
    "# Matrix size parameters.\n",
    "n = 20\n",
    "m = 10\n",
    "p = 5\n",
    "\n",
    "# Generate random problem data.\n",
    "tmp = np.random.rand(n)\n",
    "A = np.random.randn(m, n)\n",
    "b = A.dot(tmp)\n",
    "F = np.random.randn(p, n)\n",
    "g = F.dot(tmp) + np.random.rand(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Formulate and solve problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS\n",
      "\n",
      "It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT\n",
      " 0  +0.000e+00  -1.183e+01  +7e+01  1e+00  4e-01  1e+00  1e+00    ---    ---    0  0  - |  -  - \n",
      " 1  -1.045e+01  -1.419e+01  +2e+01  2e-01  1e-01  4e-01  3e-01  0.7833  5e-02   1  1  1 |  2  1\n",
      " 2  -5.864e+00  -6.905e+00  +4e+00  7e-02  3e-02  1e-01  5e-02  0.7833  5e-02   1  1  1 |  2  1\n",
      " 3  -5.590e+00  -6.018e+00  +1e+00  3e-02  1e-02  5e-02  2e-02  0.6266  5e-02   1  1  1 |  2  2\n",
      " 4  -5.525e+00  -5.621e+00  +3e-01  7e-03  3e-03  1e-02  5e-03  0.7818  1e-02   1  1  1 |  1  1\n",
      " 5  -5.490e+00  -5.530e+00  +1e-01  3e-03  1e-03  5e-03  2e-03  0.6266  5e-02   1  1  1 |  2  2\n",
      " 6  -5.484e+00  -5.493e+00  +3e-02  7e-04  3e-04  1e-03  4e-04  0.7833  1e-02   1  1  1 |  1  1\n",
      " 7  -5.482e+00  -5.485e+00  +1e-02  3e-04  1e-04  4e-04  2e-04  0.6266  5e-02   2  1  1 |  2  2\n",
      " 8  -5.481e+00  -5.482e+00  +2e-03  6e-05  3e-05  1e-04  4e-05  0.7833  1e-02   1  1  1 |  1  1\n",
      " 9  -5.481e+00  -5.481e+00  +1e-03  3e-05  1e-05  4e-05  2e-05  0.6266  5e-02   1  1  1 |  2  2\n",
      "10  -5.481e+00  -5.481e+00  +2e-04  6e-06  3e-06  9e-06  3e-06  0.7833  1e-02   2  1  1 |  1  1\n",
      "11  -5.481e+00  -5.481e+00  +9e-05  2e-06  1e-06  4e-06  1e-06  0.6266  5e-02   1  0  0 |  2  2\n",
      "12  -5.481e+00  -5.481e+00  +2e-05  5e-07  2e-07  8e-07  3e-07  0.7833  1e-02   1  0  0 |  1  1\n",
      "13  -5.481e+00  -5.481e+00  +8e-06  2e-07  1e-07  3e-07  1e-07  0.6266  5e-02   2  0  0 |  2  2\n",
      "14  -5.481e+00  -5.481e+00  +2e-06  5e-08  2e-08  7e-08  3e-08  0.7833  1e-02   1  0  0 |  1  1\n",
      "15  -5.481e+00  -5.481e+00  +7e-07  2e-08  9e-09  3e-08  1e-08  0.6266  5e-02   0  0  0 |  2  2\n",
      "16  -5.481e+00  -5.481e+00  +2e-07  4e-09  2e-09  7e-09  3e-09  0.7833  9e-03   0  0  0 |  1  1\n",
      "17  -5.481e+00  -5.481e+00  +6e-08  2e-09  8e-10  3e-09  1e-09  0.6266  5e-02   1  0  0 |  2  2\n",
      "18  -5.481e+00  -5.481e+00  +1e-08  4e-10  2e-10  6e-10  2e-10  0.7833  9e-03   1  0  0 |  1  1\n",
      "\n",
      "OPTIMAL (within feastol=4.0e-10, reltol=2.7e-09, abstol=1.5e-08).\n",
      "Runtime: 0.003436 seconds.\n",
      "\n",
      "\n",
      "The optimal value is: 5.480901488005442\n",
      "\n",
      "The optimal solution is:\n",
      "[0.43483319 0.66111715 0.49201039 0.3603062  0.3841663  0.30283659\n",
      " 0.4173023  0.79107794 0.76667303 0.38292364 1.2479328  0.50416987\n",
      " 0.68053833 0.67163957 0.13877258 0.5248668  0.08418897 0.56927148\n",
      " 0.50000247 0.78291311]\n"
     ]
    }
   ],
   "source": [
    "# Entropy maximization.\n",
    "x = cp.Variable(shape=n)\n",
    "obj = cp.Maximize(cp.sum(cp.entr(x)))\n",
    "constraints = [A*x == b,\n",
    "               F*x <= g ]\n",
    "prob = cp.Problem(obj, constraints)\n",
    "prob.solve(solver=cp.ECOS, verbose=True)\n",
    "\n",
    "# Print result.\n",
    "print(\"\\nThe optimal value is:\", prob.value)\n",
    "print('\\nThe optimal solution is:')\n",
    "print(x.value)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
